
public class Solution {
    public static void main(String[] args) {

    }

    public static int positive(int[][] arr) {
        int len = arr.length;
        int[][] f = new int[len][len];
        f[0][0] = arr[0][0];
        int temp = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (j == 0) {
                    f[i][j] = arr[i - 1][j] + arr[i][j];
                } else if (i == j) {
                    f[i][j] = f[i - 1][j - 1] + arr[i][j];
                } else {
                    f[i][j] = Math.max(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
                }
            }
        }

        for (int i = 0; i < len; i++) {
            if (f[len - 1][i] > temp) {
                temp = f[len - 1][i];
            }
        }
        return temp;
    }
}

/*动态规划比回溯法效率更高*/
/*动态规划题目类型：
* 1.计数： 有多少种方式走到右下角，有多少种方式选出k个数使得和为sum；
* 2.求最值问题： 从左上角走到右下角的最大数字和， 最长上升子序列长度；
* 3.求存在性： 取石子游戏先手是否获胜，能不能选出k个数使和是sum；
*
* 动态规划组成部分一：确定状态
*   状态在动态规划中十分重要
*   动态规划需要开一个数组，数组的每个元素f【i】或者f【i】【j】分别代表什么
*       ——类似与数学中的xyz
*   确定状态需要两个意识 ：子问题，最后一步*/

